#include <iostream>
#include <cstdio>
using namespace std;
int n;
int ans;
int ranks[15];//ranks[i]=j 第i行棋子放在第j列
bool col[15];//col[y]=true/false 第y列放置过棋子/没放过
bool lv[30];//左倾对角线 x-y
bool rv[30];//右倾对角线 x+y
/*
右
(1,1)              2
(2,1)(1,2)         3
(3,1)(2,2)(1,3)     4
(6,1)(5,2)(4,3)(3,4)(2,5)(1,6)  7
(6,4)(5,5)(4,6)                10
  
 */
void dfs(int d){
	if(d==n){//放完了n个棋子
		ans++;
		if(ans<=3){//输出前个解
			for(int i=1;i<=n;i++){
				cout<<ranks[i]<<" ";
			}
			cout<<endl;
		}
		return ;
	}
	
	for(int j=1;j<=n;j++){
		//   (d+1,j)
		int x=d+1,y=j;//棋子放置的位置
		if(!col[y] && !lv[x-y+n] && !rv[x+y]){//判断列、对角线是否重复
			col[y]=1;
			lv[x-y+n]=1;
			rv[x+y]=1;
			ranks[x]=y;
			//x-y
			dfs(d+1);
			col[y]=0;
			lv[x-y+n]=0;
			rv[x+y]=0;
			
		}
		
	}
	
}
int main(){
	cin>>n;
	dfs(0);
	cout<<ans;		
	return 0;
}
